Design a Snake game that is played on a device with screen size height x width. Play the game online if you are not familiar with the game.
The snake is initially positioned at the top left corner (0, 0) with a length of 1 unit.
You are given an array food where food[i] = (ri, ci) is the row and column position of a piece of food that the snake can eat. When a snake eats a piece of food, its length and the game's score both increase by 1.
Each piece of food appears one by one on the screen, meaning the second piece of food will not appear until the snake eats the first piece of food.
When a piece of food appears on the screen, it is guaranteed that it will not appear on a block occupied by the snake.
The game is over if the snake goes out of bounds (hits a wall) or if its head occupies a space that its body occupies after moving (i.e. a snake of length 4 cannot run into itself).
Implement the SnakeGame class:
SnakeGame(int width, int height, int[][] food)Initializes the object with a screen of sizeheight x widthand the positions of thefood.int move(String direction)Returns the score of the game after applying onedirectionmove by the snake. If the game is over, return-1.
Example 1:
Input
["SnakeGame", "move", "move", "move", "move", "move", "move"]
[[3, 2, [[1, 2], [0, 1]]], ["R"], ["D"], ["R"], ["U"], ["L"], ["U"]]
Output
[null, 0, 0, 1, 1, 2, -1]
Explanation
SnakeGame snakeGame = new SnakeGame(3, 2, [[1, 2], [0, 1]]);
snakeGame.move("R"); // return 0
snakeGame.move("D"); // return 0
snakeGame.move("R"); // return 1, snake eats the first piece of food. The second piece of food appears
// at (0, 1).
snakeGame.move("U"); // return 1
snakeGame.move("L"); // return 2, snake eats the second food. No more food appears.
snakeGame.move("U"); // return -1, game over because snake collides with border
Constraints:
1 <= width, height <= 1041 <= food.length <= 50food[i].length == 20 <= ri < height0 <= ci < widthdirection.length == 1directionis'U','D','L', or'R'.- At most
104calls will be made tomove.
Average Rating: 4.33 (12 votes)
Solution
Overview
Who doesn't feel nostalgic while thinking about the famous Snake video game? It used to be (and still is) the goto video game on phones and other platforms for so many of us and there are countless variations of the game out there. The version that this problem talks about is the most basic one. And this being a design problem makes things more interesting!
Let's go over the details in the problem statement once.
- We're given the
widthandheightof the grid over which the snake moves. - Additionally, we are also given the list of grid positions where the food would appear one after the other. Just like the traditional snake, the next food item only appears once the current one is consumed.
- Consuming a piece of food increasses the length of the snake by one. In terms of our problem statement, the length of the snake is increased by one more
cellfrom the grid with each cell being of unit length and width. - The snake can move in four directions
U,D,L, andR. Everytime the snake has to be moved, themove()function would be called and this is the only function we need to focus on in this question. - The game ends when either of these conditions happens:
- The snake becomes too long to potentially fit inside the grid or
- The snake hits one of the boundaries which would happen in the previous case as well.
- The snake bites itself i.e. when the head of the snake collides with its body in the next move.
The problem statement doesn't have any follow up statements, but we're going to discuss a follow-up to this question where the wall becomes infinite i.e. the snake can move across walls and the only condition then for the game to end is when the snake crashes into itself on the grid.
Approach: Queue and Hash Set
Intuition
Let's start by thinking about how we want to store the snake?
In terms of the grid, a snake is just an ordered collection of cells.
We can technically use an array to store the cells representing a snake. However, we would need to instantiate an array the size of width * height of the grid since a snake can be composed of all the the cells of the grid in the worst case. A spiral kind of a snake. Let's look at such a snake occupying the grid.
This structure is highly unlikely given the random nature of food items appearing on the grid. However, we would need an array the size of the grid to be able to hold this big a snake. The breaking point for an array is when we have to move the snake from one position to another. Let's see what happens to the snake when it moves by one in a direction. The result overall would be the same with some minor changes based on the direction.
In the above figure, we have a snake that occupies 4 cells across the grid or in other words, is of length 4. The snake can be represented by the following collection of cells: [(1,1), (1,2), (1,3), (2,3)]. Now say we have the snake move in the right direction i.e. R. The snake now would look like this across the grid.
Now here, after moving one step to the right, the snake is represented by the cells [(1,2), (1,3), (2,3), (2,4)].
In order to achieve this with an array, we would have to move all the cells around per move which is not exactly ideal. We can build some complicated logic around the movement of the snake in an array but that won't be worth the fixed space complexity that an array would occupy.
Let's see what data structure would naturally fit our requirements for the snake. There are two basic requirements we need to satisfy:
- Dynamically add new cells to the snake's body and
- Move the snake in constant amount of time across the grid.
Let's look at the snake representation between moves from the example above to understand what really is happening here and that will help us get to the data structure we need to use for solving this problem.
Move with No Food
We already have an example for such a move so we will simply be looking at the snake representation on the grid to understand what's really happening here.
Before the move, the snake was occupying the following cells of the grid in the specified order:
(1,1), (1,2), (1,3), (2,3)
and after the move, the snake was occupying the following positions on the grid:
(1,2), (1,3), (2,3), (2,4)
If you think about this from a sliding window perspective, we simply moves the window one step forward i.e. we removed the tail of the window and added a new head to the window. The tail in this case was (1,2) and the new head being (2,4).
Move with Food Consumption
Now let's look at a move by the snake wherein they consume a food item and grow in length. Suppose the move was the same as before and the spot (2,4) contained a food item. The snake head from the previous example, was at (2,3) on the grid. So, a move to the right would cause them to consume this food item thus extending their overall length by one. So now, instead of occupying 4 cells on the grid, the snake would occupy 5 cells. Let's concretely look at the snake representations before and after the move.
Before the move, the snake was occupying the following cells of the grid in the specified order:
(1,1), (1,2), (1,3), (2,3)
and after the move, the snake was occupying the following positions on the grid:
(1,1), (1,2), (1,3), (2,3), (2,4)
Here, we simply added a new head to the snake with the head being the cell (2,4). The tail remained the same in this case. These are the only two possibilities for moves that can happen other than the termination conditions for the game. Based on them, let's see what operations out data structure needs to support concretely for us to be able to perform these moves efficiently.
Our abstract data structure needs to support the following operations efficiently.
- Grow in size dynamically. Note that we never shrink in size. The snake can stay the same size as before or grow in size due to the consumption of a food item on the grid. But they can't shrink in size.
- Maintain a specified ordering of cells in order to represent the snake.
- Extract the
tailcell and potentially add a newheadcell to the ordering of cells to represent the updated snake post a move. This is the most important operation of all and this points to a very specific data structure.
Based on the third operation, we can see that the Queue would be a good data structure to use since we need to have quick access to the first and last elements of an ordered list and a queue gives us exactly that.
A queue is an abstract data structure with some specified properties which meets our requirements. It can be represented by an array or a linked list. For our purposes, since we need a data structure with dynamic sizing, we would go with a linked-list based implementation for a queue rather than an array since we don't want to pre-allocate any memory for the array and only allocate on the fly. A linked list would be a great fit here since we don't require random access to cells of the snake.
Algorithm
-
Initialize a queue containing a single cell
(0,0)which is the initial position of the snake at the beginning of the game. Note that we will be doing this in the constructor of the class and not in themovefunction. -
The fist thing we need to do inside the
movefunction is to compute the new head based on the direction of the move. As we saw in the intuition section, irrespective of the kind of move, we will always get a new head. We need the new head position to determine if the snake has hit a boundary and hence, terminate the game. -
Let's first discuss the termination conditions before moving on to the modifications we would make to our queue data structure.
- The first condition is if the snake cross either of the boundaries of the grid after the mode, then we terminate. So for this, we simply check if the new head (
new_head) satisfiesnew_head[0] < 0ornew_head[0] > heightornew_head[1] < 0ornew_head[1] > width. - The second condition is if the snake bites itself after the move. An important thing to remember here is that the current
tailof the snake is not a part of the snake's body. If the move doesn't involve a food, then the tail gets updated (removed) as we have seen. If this is a food move, then the snake cannot bite itself because the food cannot appear on any of the cells occupied by the snake (according to the problem statement).
In order to check if the snake bites itself we need to check if the new head already exists in our queue or not. This can turn out to be an O(N) operation and that would be costly. So, at the expense of memory, we can also use an additional dictionary data structure to keep the positions of the snake. This dictionary will only be used for this particular check. We can't do with just a dictionary because a dictionary doesn't have an ordered list of elements and we need the ordering for our implementation.
- The first condition is if the snake cross either of the boundaries of the grid after the mode, then we terminate. So for this, we simply check if the new head (
-
If none of the termination conditions have been met, then we will continue to update our queue with the new head and potentially remove the old tail. If the new head lands on a position which contains food, then we simply add the new head to our queue representing the snake. We won't pop the tail in this case since the length of the snake has increased by 1.
-
After each move, we return the length of the snake if this was a valid move. Else, we return
-1to indicate that the game is over.
Complexity Analysis
Let W represent the width of the grid and H represent the height of the grid. Also, let N represent the number of food items in the list.
- Time Complexity:
- The time complexity of the
movefunction is O(1). - The time taken to calculate
bites_itselfis constant since we are using a dictionary to search for the element. - The time taken to add and remove an element from the queue is also constant.
- The time complexity of the
- Space Complexity:
- The space complexity is O(W×H+N)
- O(N) is used by the
fooddata structure. - O(W×H) is used by the
snakeand thesnake_setdata structures. At most, we can have snake that occupies all the cells of the grid as explained in the beginning of the article.
January 13, 2021 10:14 AM
You could just use a set for checking if the snake bites itself Instead of a dictionary.
November 21, 2020 1:09 PM
Has to be HARD difficulty isnt it?
April 15, 2021 3:46 AM
This isn't very hard if you just start to do it and live with the fact that you need half a dozen class vars. One disappointment is in AC and test case it expects snake to move its tail first then the head, which is not how nature works and actually produces more corner cases this way.
class SnakeGame {
private final int W;
private final int H;
private final Map<String, int[]> dir = new HashMap<>();
private final int[][] food;
private int currFood = 0;
private int score = 0;
private final Deque<Integer> queue = new LinkedList<>();
private final Set<Integer> snake = new HashSet<>();
private int r = 0;
private int c = 0;
/** Initialize your data structure here.
@param width - screen width
@param height - screen height
@param food - A list of food positions
E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
public SnakeGame(int width, int height, int[][] food) {
W = width;
H = height;
this.food = food;
dir.put("U", new int[] {-1,0});
dir.put("D", new int[] {1,0});
dir.put("L", new int[] {0,-1});
dir.put("R", new int[] {0,1});
queue.add(0);
snake.add(0);
}
/** Moves the snake.
@param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
@return The game's score after the move. Return -1 if game over.
Game over when snake crosses the screen boundary or bites its body. */
public int move(String direction) {
int[] d = dir.get(direction);
r += d[0];
c += d[1];
if (r < 0 || r == H || c < 0 || c == W) return -1;
int hash = r * 100000 + c;
// there is an ambiguity should the tail move first or the head move first
// by observing nature the head should that it can eat its tail
// but test case says tail move first, that produces more "corner cases" like duplicated hash
if (snake.contains(hash) && hash != queue.peekLast()) return -1;
if (currFood < food.length && r == food[currFood][0] && c == food[currFood][1]) {
score++;
currFood++;
} else {
snake.remove(queue.removeLast());
}
// head can occupy previous tail location, remove tail then add head
queue.addFirst(hash);
snake.add(hash);
return score;
}
}
/**
* Your SnakeGame object will be instantiated and called as such:
* SnakeGame obj = new SnakeGame(width, height, food);
* int param_1 = obj.move(direction);
*/
Last Edit: April 28, 2021 1:50 PM
An observation: The problem description provides these constraints:
1 <= width, height <= 10^4
1 <= food.length <= 50
The maximum amount of food is tiny. Given this, the snake can never be longer than 51 segments. As a consequence:
(1) The snake does not require O(W * H) memory. That would mean a potential worst case of O(10^4 x 10^ 4) = O(100,000,000) memory. (In some languages, like Python this might require 1GB of RAM or more, given the overhead with objects and arrays!)
Instead, it requires O(f) memory, where f is the amount of food. For practical purposes, this is equivalent to O(1) memory.
(2) For similar reasons, there isn't a Big-O performance benefit from using a separate hash set to store the snake's segment positions. In Python, you can simply iterate over the deque -- which contains at most O(51) segments -- to check for collisions. This simplifies the code substantially and eliminates a class variable:
# Have we collided with the tail?
if (row, col) in self.snake:
return -1
(In other languages, this might be more difficult, but not impossible.)
Using a hash set might be an optimization, but it doesn't provide a meaningful Big-O improvement in performance. In practice, I had exactly the same timings on LeetCode (240ms) for both approaches.
You can also simplify the code further by reversing the food list and storing it as a stack. Then, when the snake consumes food, you can pop that food item off the stack.
My complete code is below:
class SnakeGame:
def __init__(self, width: int, height: int, food: List[List[int]]):
self.snake = collections.deque([(0, 0)])
self.food = list(reversed(food))
self.width = width
self.height = height
self.directions = {
"U": (-1, 0),
"D": (1, 0),
"L": (0, -1),
"R": (0, 1)
}
def move(self, direction: str) -> int:
# Get new coordinates of snake head
drow, dcol = self.directions[direction]
row, col = self.snake[-1][0] + drow, self.snake[-1][1] + dcol
# Are we out of bounds?
if not (0 <= row < self.height and 0 <= col < self.width):
return -1
# Is there food at this position?
if self.food and row == self.food[-1][0] and col == self.food[-1][1]:
self.food.pop() # Consume the food
else:
tail = self.snake.popleft() # Contract the tail by one segment
# Have we collided with the tail?
if (row, col) in self.snake:
return -1
# Advance the head
self.snake.append((row, col))
# Return the current score
return len(self.snake) - 1
Last Edit: March 31, 2021 9:00 AM
I am not seeing any need for snake HashMap<Pair<>>, HashSet<Pair<>> should be good enough? Am I missing something. Is Pair<> not compatible with HashSet?
not only are companies asking algo bs, we have to learn this? I think this is more practical than doing binary tree problems .
February 3, 2021 11:01 PM
How could you use Pair class in hash without overriding the equal() and hashCode()?
January 27, 2021 1:35 AM
I think the space complexity can be summed up by O(N), because as you mentioned, the worst case scenario is the body of the snake filling every single tile given by the width and height. However, you need food to make the snake grow, and if the snake filled the tiles, it will be O(3N), 1N for food structure, 1N for snake body in deque, and 1N for the set containing the indices.
You don't have any submissions yet.
xxxxxxxxxxclass SnakeGame {public: /** Initialize your data structure here. @param width - screen width @param height - screen height @param food - A list of food positions E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */ SnakeGame(int width, int height, vector<vector<int>>& food) { } /** Moves the snake. @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down @return The game's score after the move. Return -1 if game over. Game over when snake crosses the screen boundary or bites its body. */ int move(string direction) { }};/** * Your SnakeGame object will be instantiated and called as such: * SnakeGame* obj = new SnakeGame(width, height, food); * int param_1 = obj->move(direction); */